//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
// 
//
// 示例 2： 
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0] 
//
// 
//
// 限制： 
//
// 
// 0 <= k <= arr.length <= 10000 
// 0 <= arr[i] <= 10000 
// 
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 446 👎 0

package leetcode.editor.cn;

import java.util.PriorityQueue;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer40 {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k ==0) return new int[0];
        PriorityQueue<Integer> queue = new PriorityQueue<>(k,((o1, o2) -> o2.compareTo(o1)));
        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }
        for(int i = k; i < arr.length; i++){
            if(arr[i] < queue.peek()){
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        int[] result = new int[k];
        for(int i = 0; i < k; i++){
            result[i] = queue.poll();
        }
        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
